


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import defaultdict

        need,window = defaultdict(int),defaultdict(int)
        left = right = 0
        valid = 0
        start,length = 0,float('inf')

        for c in t:
            need[c] += 1

        while right < len(s):
            c = s[right]
            right += 1

            #窗口数据更新
            if c in need:
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1
            
            
            #z左指针开始移动
            while valid == len(need):
                
                #记录长度
                if right - left < length:
                    start = left
                    length = right - left
                
                #更新窗口数据
                d = s[left]
                left += 1

                if d in need:
                    if need[d] == window[d]:
                        valid -= 1
                    window[d] -= 1
        return "" if length == float('inf') else s[start:start + length]